#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
//class Solution {
//public:
//    void sortColors(vector<int>& nums) {
//        int col[3] = { 0 }, i = 0;
//        for (auto i : nums) col[i]++;
//        while (col[0]--) nums[i++] = 0;
//        while (col[1]--) nums[i++] = 1;
//        while (col[2]--) nums[i++] = 2;
//    }
//};

class Solution {
public:
    void _sortColors(vector<int>& nums, int left, int right)
    {
        int n = 1, begin = left, end = right;
        for (int i = left; i <= right;)
        {
            if (nums[i] < n) swap(nums[left++], nums[i++]);
            else if (nums[i] == n) i++;
            else swap(nums[right--], nums[i]);
        }
    }
    void sortColors(vector<int>& nums) {
        _sortColors(nums, 0, nums.size() - 1);
    }
};

int main()
{
    Solution s;
    vector<int> v({ 2,0,2,1,1,0 });
    s.sortColors(v);
    return 0;
}